#include <stdio.h>
#include <stdlib.h>

struct list 
{
  struct list * prev;
  struct list * next;
  int value;
  int index;
};

struct list * head;

void add(struct list * node)
{
  struct list * src, * prev;

  if (head == NULL)
    return;

  src = head;  // 头结点,全局变量.当前结点.
  prev = src;  // 前结点.

  while (src->next != NULL) {
    if (src->value <= node->value) { // 后移
      prev = src;	  // 前结点.
      src = src->next;    // 下结点.
    }
    else {
      prev->next = node;  // 前结点指向新点.
      node->prev = prev;  // 新结点前驱指向前结点.
      node->next = src;   // 新结点后驱指向下结点.
      src->prev = node;   // 下结点前驱指向新结点.即插入.
      break;
    }

    if (src == head) {    // 从头结点开始.
      prev->next = node;  // 前结点指向新点. 
      node->prev = prev;  // 新结点前驱指向前结点.
      node->next = src;   // 新结点后驱指向下结点
      src->prev = node;   // 下结点前驱指向新结点.即插入.
      break;
    }
  }

  if (src->next == NULL) { // 从空结点开始.
    prev->next = node;     // 指向新结点
    node->next = src;      // 新结点指向当前结点.
    node->prev = prev;     // 新结点前驱指向前结点.
    src->prev = node;      // 当前结点前驱指向新结点.
  }
}

void del(int value)
{
  struct list * src, * prev, * temp;

  src = head->next;  // 头结点的下结点.
  prev = src;        // 用作前结点

  while (src->next != head->next) { // prt->next 为 head->next->next, 即head->next的下一个结点.
    if (src->value == value) {
      temp = src;              // 要删除的结点.
      prev->next = src->next;  // ptr->next = 要删除的结点指针指向下结点.
      src->next->prev = prev;
      free(temp);
      printf("delete node of value is : %d\n", value);
      break;
    }
    else if (src->value < value) {
      prev = src;
      src = src->next;
    }
    else {
      printf("node\n");
      break;
    }
  }
}

struct list * new()
{
  struct list * des;

  des = (struct list *) malloc (sizeof(struct list));
  if (!des) {
    printf("allocate failure.\n");
    return NULL;
  }
  else {
    des->value = -1;
    des->index = -1;
    des->prev = NULL;
    des->next = NULL;

    return des;
  }
}

void display(int order)
{
  struct list * src;
  int i = 1;

  if (!order) {
    src = head->next;
    printf("up order:\n");
    while (src->next != head->next) {
      printf("i = %d : %d\n", i++, src->value);
      src = src->next;
    }
  }
  else {
    src = head->prev;
    printf("down order:\n");
    while (src->prev != head->prev) {
      printf("i = %d : %d\n", i++, src->value);
      src = src->prev;
    }
  }
}

int main()
{
  struct list * des;
  int i;

  head = new();
  if (head == NULL)
    exit(-1);

  for (i = 0; i < 10; i++) {
    des = new();
    des->value = i;
    des->index = i + 1;
    add(des);
  }
  
  display(0);
  del(2);
  del(3);
  del(6);
  display(0);

  des = new();
  des->value = 88;
  des->index = 88;
  add(des);
  display(0);

  des = new();
  des->value = 77;
  des->index = 77;
  add(des);
  display(0);
  
  des = new();
  des->value = 66;
  des->index = 66;
  add(des);
  display(0);
}
